package 回溯;

import java.util.LinkedList;
import java.util.List;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 全排列.java
 * @Description TODO
 * @createTime 2020年11月01日 15:53:00
 */
public class 全排列 {
    public static void main(String[] args) {

    }
    class Solution {
        List<List<Integer>> res=new LinkedList<>();
        public List<List<Integer>> permute(int[] nums) {

            //用来记录路径
            LinkedList<Integer> track=new LinkedList<>();
            backtrack(nums,track);
            return res;
        }

        //nums表示    LinkedList用来存放当前路径
        void backtrack(int[] nums,LinkedList<Integer> track){
            //结束条件
            if(track.size()==nums.length){
                res.add(new LinkedList<Integer>(track));
                return ;
            }
            //选择列表
            for(int i=0;i<nums.length;i++){
                if(track.contains(nums[i])){
                    continue;
                }
                //做选择
                track.add(nums[i]);
                //进入下一决策树
                backtrack(nums,track);
                //取消选择
                track.removeLast();

            }


        }
    }

//    class Solution {
//        List<List<Integer>> res=new LinkedList<>();
//        public List<List<Integer>> permute(int[] nums) {
//            Deque<Integer> track=new ArrayDeque<>();
//            boolean[] used = new boolean[ nums.length];
//            back(nums,track,used);
//            return res;
//        }
//
//        void back(int[] nums,Deque<Integer> track,boolean[] used){
//            if(nums.length==track.size()){
//                res.add(new ArrayList<>(track));
//                return ;
//            }
//
//            for(int i=0;i<nums.length;i++){
//                if(used[i]){
//                    continue;
//                }
//
//                track.add(nums[i]);
//                used[i]=true;
//                back(nums,track,used);
//                track.removeLast();
//                used[i]=false;
//            }
//        }
//    }


}
